package pers.qianyu.month_202012.date_20201222;

/**
 * 自定义实现优先队列
 * - 底层使用数组模拟完全二叉树
 * - 二叉树性质
 * --- 父节点 (i - 1) / 2
 * --- 左孩子 2 * i + 1
 * --- 右孩子 2 * i + 2
 *
 * @author mizzle rain
 * @date 2020-12-22 17:46
 */
public class MyPriorityQueue {
    private int[] arr;
    private int size = 0;

    public MyPriorityQueue(int cap) {
        arr = new int[cap];
    }

    /********对外暴露的函数********/
    public int peek() {
        return arr[0];
    }

    public void push(int x) {
        arr[size++] = x;
        rise(size - 1);
    }

    public int poll() {
        if (size == 0) {
            return -1;
        }
        int res = arr[0];
        swap(0, --size);
        sink(0);
        return res;
    }

    /********私有函数********/
    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private void rise(int index) {
        while (index > 0 && arr[(index - 1) >> 1] < arr[index]) {
            int parentIndex = (index - 1) >> 1;
            swap(parentIndex, index);
            index = parentIndex;
        }
    }

    private void sink(int index) {
        for (int cur = index; cur <= (size >> 1) - 1; cur++) {
            int childIndex = index * 2 + 1;
            if (childIndex + 1 < size && arr[childIndex + 1] > arr[childIndex]) {
                childIndex++;
            }
            if (arr[childIndex] > arr[cur]) {
                swap(childIndex, cur);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 3, 7, 1};
        MyPriorityQueue q = new MyPriorityQueue(100);
        for (int item : arr) {
            q.push(item);
        }
        System.out.println(q.peek());
        System.out.println(q.poll());
        System.out.println(q.poll());
        System.out.println(q.poll());
        q.push(100);
        System.out.println(q.poll());
        System.out.println(q.poll());
        System.out.println(q.poll());
    }
}
